package BinaryTree;

import org.junit.Test;

class TreeNode{
    int val;
    int upTemp;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        val = x;
        upTemp = 0;
    }
}

/**
 * 后序debug
 *  if f左
 *  if f右
 *  [+sout:
 *      左到底 -> 叶子(从左到右) -> 向上一步 -> 立刻右1 -> loop左到底叶
 *  ]
 *  pt
 *
 */
public class 二叉树中的最大路径和124 {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // root.upTemp = root.val>0?root.val:0;
        postOrder(root);
        return res;
    }
    int max3(int a, int b, int c){
        return Math.max(Math.max(a,b), c);
    }
    int max4(int a, int b, int c, int d){
        return Math.max(Math.max(Math.max(a,b), c), d);
    }
    void postOrder(TreeNode cur){


        if(cur.left != null)
            postOrder(cur.left);
        if(cur.right != null)
            postOrder(cur.right);
        System.out.println("-----后序在这里pt debug-----");
        System.out.println("cur:" + cur.val);
        int leftUpTmp =0 , rightUpTmp = 0;
        if(cur.left != null){
            leftUpTmp = cur.left.upTemp;
        }
        if(cur.right != null){
            rightUpTmp = cur.right.upTemp;
        }

        System.out.println(String.format("它的左：%d, 右：%d", leftUpTmp, rightUpTmp));

        //错 难想到 可以形成路径的暂存点 max(只cur/cur+left/cur+right)
        cur.upTemp = max3(
                   cur.val,
                cur.val + cur.left.val,
                cur.val + cur.right.val
        );
        System.out.println("包含自己的uptemp设为：" +  cur.upTemp);
        // 最大：单支 双支 自己
        res = max4(
                cur.val + Math.max(leftUpTmp, rightUpTmp),
                cur.val + leftUpTmp + rightUpTmp,
                cur.val,
                res
        );
        System.out.println("当前最大"+res);
    }
    
    @Test
    public void test(){
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(7);
        TreeNode t3 = new TreeNode(-10);
        TreeNode t4 = new TreeNode(-2);
        TreeNode t5 = new TreeNode(3);
        TreeNode t6 = new TreeNode(1);
        TreeNode t7 = new TreeNode(2);
        TreeNode t8 = new TreeNode(1);
        TreeNode t9 = new TreeNode(4);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t3.left = t5;
        t3.right = t6;
        t5.left = t7;
        t5.right = t8;
        t8.right = t9;
        res = maxPathSum(t1);
        System.out.println("res:" + res);
    }
}
